package test.n00200;


import java.util.ArrayList;
import java.util.List;

public class Problem00220 {
    public static void main(String[] args) {
        println(3);
        println(5);
    }

    public static void println(int n) {
        Solution ss = new Solution();
        System.out.println(n + "," + ss.generateParenthesis(n));
    }

    private static class Solution {

        /**
         * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
         * <p>
         * 提示：
         * <p>
         * 1 <= n <= 8
         * <p>
         * 解题思路:
         * 暴力
         *
         * @param n
         * @return
         */
        public List<String> generateParenthesis(int n) {
            List<String> list = new ArrayList<>();
            getAll(new char[2 * n], 0, list);
            return list;
        }

        public void getAll(char[] current, int pos, List<String> result) {
            if (current.length == pos) {
                if (isValid(current)) {
                    result.add(new String(current));
                }
            } else {
                current[pos] = '(';
                getAll(current, pos + 1, result);
                current[pos] = ')';
                getAll(current, pos + 1, result);
            }
        }

        private boolean isValid(char[] current) {
            int balance = 0;
            for (int i = 0; i < current.length; i++) {
                if (current[i] == '(') {
                    balance++;
                } else {
                    balance--;
                }

                if (balance < 0) {
                    return false;
                }
            }
            return balance == 0;
        }
    }
}
